<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>选择排序</title>
</head>
<body>
    <script>
        /** 选择排序
         * 
         * 工作原理：开启一个循环，每轮从未排序区间选择一个最小的元素，放到已排序区间的末尾
         * 
         * 设数组长度为 n
         * 1.初始状态，未排序区间[0,n-1]
         * 2.选取[0,n-1]区间中的最小元素，与索引为 0 的元素交换。完成后，数组已有 1 个元素完成排序
         * 3.选取[1,n-1]区间中的最小元素，与索引为 1 的元素交换。完成后，数组已有 2 个元素完成排序
         * 4.以此类推。经过 轮选择与交换后，数组前 n-1 个元素已排序。
         * 5.仅剩的一个元素必定是最大元素，无须排序，因此数组排序完成。
         * 
         * 时间复杂度：O(n2)
         * 空间复杂度：O(1)
         */

        let data = [5,6,4,7,3,8,2,9,1,0,6,5,7]

        function selectionSort(arr) {
            const a = [...arr]
            const length = a.length;
            for (let i = 0; i < length - 1; i++) {
                let minValueIndex = i

                // 内循环，找到未排序区间的最小元素的索引值
                for (let j = i; j < length; j++) {
                    if(a[j] < a[minValueIndex]) {
                        minValueIndex = j
                    }
                }

                // 将最小元素与未排序区间的末尾元素交换
                [a[i], a[minValueIndex]] = [a[minValueIndex], a[i]]
            }
            return a
        }

        const result = selectionSort(data)
        console.log('选择排序：', result)
        document.write('选择排序：', result)
    </script>
</body>
</html>